/**
 * Created with IntelliJ IDEA.
 * Description: 牛客网OJ面试必刷题 二分查找/排序练习
 */
public class Test {
    //二分查找——1
    public int search (int[] nums, int target) {
        // write code here
        int left = 0;
        int right = nums.length - 1;
        while(left <= right) {
            int mid = (left + right) / 2;
            if(nums[mid] == target) {
                return mid;
            }else if(nums[mid] < target) {
                left = mid + 1;
            }else if(nums[mid] > target) {
                right = mid - 1;
            }
        }
        return -1;
    }

    //二维数组中的查找
    public boolean Find(int target, int [][] array) {
        if(array[0].length == 0) {
            return false;
        }
        int x = 0;
        int y = array[0].length - 1;
        while(x < array.length && y >= 0) {
            if(array[x][y] > target) {
                y--;
            }else if(array[x][y] < target) {
                x++;
            }else {
                return true;
            }
        }
        return false;
    }

    //寻找峰值
    /*
    这道题的前提是：
    1. 给定一个长度为n的数组，返回其中任何一个峰值的索引
    2. 峰值元素是指其值严格大于左右相邻值的元素
    3. 数组两个边界可以看成是最小，nums[−1]=nums[n]=−∞
    4. 峰值不存在平的情况，即相邻元素不会相等（这个条件保证了数组中一定有峰值）
        数组内部情况：要么递增，right就是峰值，要么递减，right就是峰值
                    至于其他更复杂的情况，更是存在峰值
     */
    /*
    解题思路：
    由前提3.可知，刚开始给的数组的左右两边都比自己的边界外面大
    因此我们可以设mid值
    当nums[i] < nums[i + 1]时，表示从 i 到 i + 1 是升的关系，否则就是降
    需要理解的是，如果 i 到 i + 1 是升，那么 i + 1 到 right 一定至少有一个波峰
    原因：无论如何，i + 1 到 right 要么会有一个先增后减的过程，要么就是一直递增，与right的值无关
    先增后减就一定有波峰，一直递增我们也保证了边界外小于边界的值，因此一定存在波峰
    由上述原因我们知道一个信息，就是边界一定要大于挨着边界的范围外的值
     */
    public int findPeakElement (int[] nums) {
        // write code here
        int left = 0;
        int right = nums.length - 1;
        //可以看到，每次循环结束，实际上left与right之间的数组就是一个满足条件的小数组
        //那么就保证了left ~ right之间一定存在峰值
        while(left < right) {
            int mid = (left + right) / 2;
            //nums[mid] < nums[mid + 1]，nums[mid + 1]作为新的边界，对left赋值
            if(nums[mid] < nums[mid + 1]) {
                left = mid + 1;
                //由于nums[i] != nums[i + 1]
                //因此这种情况是nums[mid] > nums[mid + 1]
                //nums[mid]作为新的边界，对right赋值
            }else {
                right = mid;
            }
        }
        //循环结束，当left == right的时候，可以看作只有一个元素的数组
        //且能保证这个数组两边的值都小于它，因此它就是峰值
        return left;
    }

    //数组中的逆序对
    //解题思路,i位置与i - 1以前的数据比较，与i - 1以前的数据是否有序无关
    //i - 1以前的数据有序可以更有利于找出比i位置大的数据
    public int InversePairs(int [] array) {
        //归并排序
        return MergeSort(array,0,array.length - 1);
    }

    //返回归并排序时统计的逆序对数量
    private int MergeSort(int[] arr,int start,int end) {
        if(start >= end) {
            return 0;
        }
        int mid = (start + end) / 2;
        int count = 0;
        count = MergeSort(arr,start,mid) % 1000000007;
        count = (MergeSort(arr,mid + 1,end) + count) % 1000000007;
        int[] nums = new int[end - start + 1];
        int left1 = start;
        int left2 = mid + 1;
        int i = 0;
        while(left1 <= mid && left2 <= end) {
            if(arr[left1] <= arr[left2]) {
                nums[i++] = arr[left1++];
            }else {
                nums[i++] = arr[left2++];
                count = (mid - left1 + 1 + count) % 1000000007;
            }
        }
        while(left1 <= mid) {
            nums[i++] = arr[left1++];
        }
        while(left2 <= end) {
            nums[i++] = arr[left2++];
        }
        for(i = 0; i < end - start + 1; i++) {
            arr[start + i] = nums[i];
        }
        return count;
    }

    //旋转数组的最小数字
    public int minNumberInRotateArray(int [] array) {
        //先比较第一个和最后一个，确认是否旋转
        int len = array.length;
        if(array[0] < array[len - 1]) {
            return array[0];
        }
        int left = 0;
        int right = len - 1;
        while(left < right) {
            int mid = (left + right) / 2;
            if(array[mid] < array[right]) {
                right = mid;
                //二分查找只适用于没有相同元素的情况
                //出现1,0,1,1,1或1,1,1,0,1的情况时
                //无法利用二分法判断，那么就让right逐步减小确认
            }else if(array[mid] == array[right]){
                right--;
            }else {
                left = mid + 1;
            }
        }
        return array[left];
    }

    //比较版本号
    //方式一
    public int compare1 (String version1, String version2) {
        // write code here
        int i = 0;
        int j = 0;
        int len1 = version1.length();
        int len2 = version2.length();
        while(i < len1 || j < len2) {
            int val1 = 0;
            int val2 = 0;
            while(i < len1 && version1.charAt(i) != '.') {
                val1 = val1 * 10 + version1.charAt(i) - '0';
                i++;
            }
            i++;
            while(j < len2 && version2.charAt(j) != '.') {
                val2 = val2 * 10 + version2.charAt(j) - '0';
                j++;
            }
            j++;
            if(val1 > val2) {
                return 1;
            }else if(val1 < val2){
                return -1;
            }
        }
        return 0;
    }

    //方式二：split方法
    public int compare (String version1, String version2) {
        // write code here
        String[] str1 = version1.split("\\.");
        String[] str2 = version2.split("\\.");
        int len = Math.max(str1.length, str2.length);
        for(int i = 0; i < len; i++) {
            int num1 = i < str1.length ? Integer.parseInt(str1[i]) : 0;
            int num2 = i < str2.length ? Integer.parseInt(str2[i]) : 0;
            if(num1 < num2) {
                return -1;
            }else if(num1 > num2) {
                return 1;
            }
        }
        return 0;
    }
}
